The present invention relates to a data compression apparatus for a facsimile system or the like.
In a facsimile system an original document is optoelectronically scanned to produce binary data signals representing light and dark areas of the document. These data signals are transmitted to a remote receiver over a telephone line or the like. The receiver reproduces the original document based on the received data signals.
In most cases the data signals contain a high degree of redundancy. Especially in the case of a white sheet of paper containing only a few characters or designs, the white background areas constitute mostly redundant data.
It is always desirable to increase the transmission speed in facsimile systems. Not only can more documents be transmitted in a given period of time, but the transmission time per document is reduced. Especially where facsimile transmission is performed via overseas telephone lines, it is desirable to reduce the transmission time and thereby the telephone charges.
Compressing the data signals so as to reduce the degree of redundancy provides an advantageous way of increasing transmission speed. Typical of such compression methods is run length encoding in which the data signals themselves are not transmitted. Instead, the numbers of consecutive data signals of the same logical value (representing black or white areas of the document) are counted and codes corresponding to these counts are transmitted. For example, if a data run consisting of 9 consecutive logically low (white area) bits is counted, the binary code 1001 may be transmitted. Although codes indicating whether the run lengths are for high or low bits may also be transmitted, such codes are redundant in that runs of logically low bits must necessarily follow runs of logically high bits and vice-versa.
In one dimensional run length data compression, the data runs are limited to one scan line. In other words, one scan line is run length encoded, the process interrupted, and then the next scan line is encoded. Even if a data run extends from one scan line to another, the scan lines are separated.
Although one dimensional compression demonstrates a very low error rate, the degree of compression or the compression ratio is rather limited.
The one dimensional compression process may be extended to a two dimensional compression process know as batch encoding in which a predetermined number of scan lines are encoded in a batch. In this case, runs may extend between lines in the batch.
A third type of data compression is known as sequential two dimensional processing in which the vertical correlation between each two adjacent scan lines is taken into account to further reduce the redundancy and increase the degree of compression. Generally, for documents containing a large amount of blank spaces sequential two dimensional compression provides a compression ratio which is 1.2 to 2 times greater than for one dimensional compression. However, for complicated patterns where there is little or no correlation between adjacent scan lines, the compression ratio with sequential two dimensional compression is lower than that with one dimensional compression.
Another problem inherent in two dimensional data compression is that the effects of a data error tend to be passed on to subsequent scan lines. In two dimensional batch processing, the extension of error is limited to the number of scan lines in the batch.
A prior art attempt to prevent the propogation of error in sequential two dimensional compression involves automatically subjecting every fourth scan line, for example, to one dimensional rather than two dimensional compression. Although this expedient does succeed in limiting propogation of error to four scan lines, it also seriously deteriorates the overall compression ratio of the system.